

/**
 * 在一个nxm矩阵形状的城市里爆发了洪水，洪水从(0,0)的格子流到这个城市，
 * 在这个矩阵中有的格子有一些建筑，洪水只能在没有建筑的格子流动。
 * 请返回洪水流到(n - 1,m - 1)的最早时间
 * (洪水只能从一个格子流到其相邻的格子且洪水单位时间能从一个格子流到相邻格子)。
 * 给定一个矩阵map表示城市，其中map[i][j]表示坐标为(i,j)的格子
 * 值为1代表该格子有建筑，0代表没有建筑。
 * 请返回流到(n - 1,m - 1)的最早时间。保证洪水一定能流到终点。
 */
public class Flood {
	//AC 229ms 17.86K
	//回溯法
	int n;
	int m;
	int min=Integer.MAX_VALUE;
	public int floodFill(int[][] map, int n, int m) {
		this.n=n-1;
		this.m=m-1;
		return getCount(0,0,0,map);
	}
	//回溯法
	public int getCount(int count,int n,int m,int[][] map){
		if (n>this.n||m>this.m)
			return min;
		if (this.n==n&&this.m==m)
			if (min>count)
				min=count;
		//如果没有障碍物
		if (map[n][m]==0)
			count++;
		//撞到墙了，回退
		else {
			return 0;
		}
		getCount(count,n+1,m,map);
		getCount(count,n,m+1,map);
		return min;
	}

	public static void main(String[] args) {
		//答案59
		int[][] map={
				{0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0},
				{0,1,1,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1,1,0},
				{0,1,1,0,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1,1,0,1},
				{0,1,1,1,0,1,1,0,0,0,1,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,0},
				{0,1,1,1,1,0,1,0,0,1,0,1,0,0,1,0,1,1,1,0,1,0,0,1,1,1,0},
				{0,0,1,0,0,0,1,1,0,0,1,1,1,1,1,1,0,1,0,0,0,0,1,0,1,0,0},
				{0,0,0,1,0,0,0,1,1,0,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0},
				{0,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,1,1,1,1,1,1,0,0,0},
				{0,0,0,0,1,0,0,1,0,1,1,0,1,1,0,1,1,1,1,0,0,0,0,0,0,1,1},
				{0,0,1,1,1,0,1,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,0},
				{0,1,0,0,1,0,0,1,0,1,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,1,1},
				{0,0,0,0,0,0,1,1,1,1,0,1,1,1,0,0,1,1,0,0,1,1,0,1,0,1,1},
				{0,0,1,1,0,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,0,0,0,1,1,0},
				{0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,0},
				{0,1,0,0,1,1,0,1,0,1,0,1,0,0,1,1,0,0,1,1,0,1,0,1,0,0,1},
				{0,1,0,1,0,1,0,0,0,0,0,1,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1},
				{0,0,1,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,0,1,0},
				{0,1,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,1,0,1,1,0,0,0},
				{0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1,0,0,1,1,0,1,1,1,1,0,0},
				{0,0,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1},
				{0,1,0,0,1,0,0,1,1,0,0,1,1,1,1,1,0,1,0,1,0,1,1,0,1,1,1},
				{0,0,1,1,1,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,0},
				{0,1,1,0,1,1,1,1,1,1,0,0,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1},
				{0,0,1,1,1,0,1,1,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,1,1,0,1},
				{0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,0,0,1,1,0,0,0},
				{0,1,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,1,1,0,1,1,0,1},
				{0,1,1,0,0,1,1,0,0,0,0,1,0,1,1,1,1,1,0,1,0,1,1,0,0,0,1},
				{0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1},
				{0,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,1,1,0,1,1,1},
				{0,0,0,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,0,0,0},
				{0,0,1,0,0,1,1,0,1,0,0,0,1,1,1,1,1,1,1,1,1,0,0,1,0,1,1},
				{0,1,0,1,1,1,1,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1,1},
				{0,0,0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,1,1,0,0,0,1},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
		};
		Flood flood=new Flood();
		System.out.println(flood.floodFill(map,34,27));
	}
}
